//编写代码，移除未排序链表中的重复节点。保留最开始出现的节点。 
//
// 示例1： 
//
// 
// 输入：[1, 2, 3, 3, 2, 1]
// 输出：[1, 2, 3]
// 
//
// 示例2： 
//
// 
// 输入：[1, 1, 1, 1, 2]
// 输出：[1, 2]
// 
//
// 提示： 
//
// 
// 链表长度在[0, 20000]范围内。 
// 链表元素在[0, 20000]范围内。 
// 
//
// 进阶： 
//
// 如果不得使用临时缓冲区，该怎么解决？ 
//
// Related Topics 哈希表 链表 双指针 👍 203 👎 0


package LeetCode.editor.cn;


import java.util.HashSet;
import java.util.Set;

/**
 * @author ldltd
 * @date 2025-06-16 21:38:26
 * @description 面试题 02.01.移除重复节点
 
 */
 
public class RemoveDuplicateNodeLcci {
    public static void main(String[] args) {
    //测试代码
    RemoveDuplicateNodeLcci fun = new RemoveDuplicateNodeLcci();
    Solution solution= fun.new Solution();
    
    }

//leetcode submit region begin(Prohibit modification and deletion)

  //Definition for singly-linked list.
  public class ListNode {
      int val;
      ListNode next;
      ListNode() {}
      ListNode(int val) { this.val = val; }
      ListNode(int val, ListNode next) { this.val = val; this.next = next; }
  }

class Solution {
        // 不适用额外空间，双重循环  时间ON2
    public ListNode removeDuplicateNodes1(ListNode head) {
        ListNode curr = head;
        while (curr != null) {
            ListNode runner = curr;
            while (runner.next != null) {
                if (runner.next.val == curr.val) {
                    runner.next = runner.next.next; // 删除重复节点
                } else {
                    runner = runner.next; // 继续往后检查
                }
            }
            curr = curr.next; // 移动到下一个节点
        }
        return head;
    }
    // 位运算
    /*
    * 用位图（BitMap）记录已经出现过的节点值，
    * 从而实现 O(n) 时间 + O(1) 空间 的去重
    * （严格来说是 O(1) 额外空间，因为位图大小固定）。
    *
    *
    * */
    public ListNode removeDuplicateNodes(ListNode head) {
        // 1. 初始化位图数组（20000 / 32 + 1 = 626，足够覆盖 0~20000）
        int[] bits = new int[20000 / 32 + 1];
        ListNode cur = head;
        while (cur != null && cur.next != null) {
            // 2. 标记当前节点的值已经出现过（设置对应 bit 为 1）  1<<cur%32表示在哪个槽，
            // cur/32表示在这个槽的第几个
            bits[cur.val / 32] |= 1 << (cur.val % 32);
            // 3. 检查下一个节点的值是否已经出现过
            if ((bits[cur.next.val / 32] & (1 << (cur.next.val % 32))) != 0)
                // 4. 如果出现过，删除下一个节点（跳过它）
                cur.next = cur.next.next;
            else
                // 5. 如果没出现过，继续遍历
                cur = cur.next;
        }
        return head;
    }

    // hash存储
    public ListNode removeDuplicateNodes3(ListNode head) {
            if (head == null) {
                return head;
            }
            Set<Integer> occurred = new HashSet<Integer>();
            occurred.add(head.val);
            ListNode pos = head;
            // 枚举前驱节点
            while (pos.next != null) {
                // 当前待删除节点
                ListNode cur = pos.next;
                if (occurred.add(cur.val)) {
                    pos = pos.next;
                } else {
                    pos.next = pos.next.next;
                }
            }
            pos.next = null;
            return head;
        }


    /**
     * 主方法：去重无序链表（先排序再去重），不保序错误
     */
    public ListNode removeDuplicateNodes2(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }

        // 1. 归并排序链表
        head = mergeSort(head);

        // 2. 删除相邻重复节点
        ListNode curr = head;
        while (curr != null && curr.next != null) {
            if (curr.val == curr.next.val) {
                curr.next = curr.next.next; // 跳过重复节点
            } else {
                curr = curr.next; // 继续遍历
            }
        }
        return head;
    }

    /**
     * 归并排序链表（递归实现）
     */
    private ListNode mergeSort(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }

        // 1. 快慢指针找中点
        ListNode mid = findMiddle(head);
        ListNode rightHead = mid.next;
        mid.next = null; // 断开链表

        // 2. 递归排序左右两部分
        ListNode left = mergeSort(head);
        ListNode right = mergeSort(rightHead);

        // 3. 合并两个有序链表
        return merge(left, right);
    }

    /**
     * 快慢指针找中点（慢指针走1步，快指针走2步）
     */
    private ListNode findMiddle(ListNode head) {
        ListNode slow = head;
        ListNode fast = head.next; // 让 slow 落在前半部分的最后一个节点
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }

    /**
     * 合并两个有序链表
     */
    private ListNode merge(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(-1);
        ListNode curr = dummy;

        while (l1 != null && l2 != null) {
            if (l1.val < l2.val) {
                curr.next = l1;
                l1 = l1.next;
            } else {
                curr.next = l2;
                l2 = l2.next;
            }
            curr = curr.next;
        }

        // 处理剩余部分
        if (l1 != null) {
            curr.next = l1;
        }
        if (l2 != null) {
            curr.next = l2;
        }

        return dummy.next;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}
